package com.future;

import java.util.HashMap;
import java.util.Map;

/**
 * Description: 1836. 从未排序的链表中移除重复元素
 *
 * @author weiruibai.vendor
 * Date: 2022/7/27 10:46
 */
public class Solution_1836 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(4);
        head.next.next.next.next.next = new ListNode(3);
        head.next.next.next.next.next.next = new ListNode(4);
        head.next.next.next.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next.next.next.next = new ListNode(9);
        head.next.next.next.next.next.next.next.next.next = new ListNode(10);
        System.out.println(deleteDuplicatesUnsorted(head));
    }


    /**
     * @param head
     * @return
     */
    public static ListNode deleteDuplicatesUnsorted(ListNode head) {
        ListNode ansHead = new ListNode(-1);
        ListNode newOp = null;
        Map<Integer, Integer> keyTimesMap = new HashMap<Integer, Integer>();
        ListNode oldOpNode = head;
        // 1、计算值出现的频率
        while (oldOpNode != null) {
            keyTimesMap.put(oldOpNode.val, keyTimesMap.getOrDefault(oldOpNode.val, 0) + 1);
            oldOpNode = oldOpNode.next;
        }
        oldOpNode = head;
        while (oldOpNode != null) {
            if (keyTimesMap.get(oldOpNode.val) == 1) {
                /**
                 * 只看频率为1的节点，newOp始终在返回链表的末尾节点
                 */
                if (newOp == null) {
                    newOp = oldOpNode;
                    ansHead.next = newOp;
                } else {
                    /**
                     * newOp的下个节点是老链表的当前节点
                     */
                    newOp.next = oldOpNode;
                    /**
                     * 移动
                     */
                    newOp = newOp.next;
                }
            }
            oldOpNode = oldOpNode.next;
        }
        /**
         * 非常注意，newOp指向新链表的最后节点，需要手动把最后节点设置为null
         */
        if (newOp != null) {
            // 需要判断是否非空
            newOp.next = null;
        }
        return ansHead.next;
    }

    private static void print(ListNode head) {
        while (head != null) {
            System.out.println(head.val + " ");
            head = head.next;
        }
    }

}
